﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

// TCO13 Round 1A DIV 1
public class RedPaint
{
    public double expectedCells3(int N)
    {
        double[,] dp = new double[5,5];
        dp[0,0]=1;
        for (int k = 1; k <= N; k++)
        {
            double[,] next = new double[5, 5];
            for (int i = k - 1; i >= 0; i--)
            {
                int j = k - i - 1;
                next[i + 1, j] += dp[i, j] * 0.5;
                next[i, j + 1] += dp[i, j] * 0.5;
            }
            dp = next;
        }

        double res = 0;
        for ( int i = N ;i >= 0 ; i-- ) {
            int j = N - i;
            res += (Math.Max(i,j)+1) * dp[i,j];
        }

        return res;
    }

    public double expectedCells(int N)
    {
        double[,] dp = new double[6, 6];
        dp[0, 0] = 1;
        for (int i = 1; i <= N; i++)
        {
            double[,] next = new double[6, 6];
            for (int j = 0; j < i; j++)
            {
                for (int k = 0; k <= j; k++)
                {
                    if (k == 0)
                    {
                        next[j + 1, k] += dp[j, k] * 0.5;
                        next[Math.Max(j, 1), 1] += dp[j, k] * 0.5;
                    }
                    else
                    {
                        next[j, k - 1] += dp[j, k] * 0.5;
                        next[Math.Max(j, k + 1), k + 1] += dp[j, k] * 0.5;
                    }
                }
            }
            dp = next;
        }
        double res = 0;
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                res += dp[i, j] * (i + 1);
            }
        }
        return res;
    }

}
